import java.util.ArrayList;
import java.util.List;

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if(root1==root2){
            return true;
        }
        if(root1==null||root2==null||root1.val!= root2.val){
            return false;
        }
        return (flipEquiv(root1.left,root2.left)&&flipEquiv(root1.right,root2.right))||(flipEquiv(root1.left,root2.right)&&flipEquiv(root1.right,root2.left));
    }










    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root==null){
            return null;
        }
        if(root.val>high){
            return trimBST(root.left,low,high);
        }
        if(root.val<low){
            return trimBST(root.right,low,high);
        }
        root.left=trimBST(root.left,low,high);
        root.right=trimBST(root.right,low,high);
        return root;
    }















    List<Integer> list=new ArrayList<>();
    public List<Integer> preorder(Node root) {
        if(root==null){
            return list;
        }
        list.add(root.val);
        for(int i=0;i<root.children.size();i++){
            preorder(root.children.get(i));
        }
        return list;
    }
}



public class project {
    boolean[] booleans;
    int count;
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        count=0;
        int len=rooms.size();
        booleans=new boolean[len];
        dfs(rooms,0);
        return count==len;
    }
    public void dfs(List<List<Integer>> rooms,int index){
        count++;
        booleans[index]=true;
        for(int i:rooms.get(index)){
            if(!booleans[i]){
                dfs(rooms,i);
            }
        }
    }




















    public int reinitializePermutation(int n) {
        int[] arr=new int[n];
        int[] tmp=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=i;
        }
        int ans=0;
        while (true){
            ans++;
            for(int i=0;i<n;i++){
                if(i%2==0){
                    tmp[i]=arr[i/2];
                }else{
                    tmp[i]=arr[n/2+(i-1)/2];
                }
            }
            if(tmp[1]==1){
                break;
            }
            for(int i=0;i<n;i++){
                arr[i]=tmp[i];
            }
        }
        return ans;
    }















    public double nthPersonGetsNthSeat(int n) {
        return n==1?1.00000:0.50000;
    }
}
